//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 
//
// 你不需要 保留 每个分区中各节点的初始相对位置。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,4,3,2,5,2], x = 3
//输出：[1,2,2,4,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [2,1], x = 2
//输出：[1,2]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 200] 内 
// -100 <= Node.val <= 100 
// -200 <= x <= 200 
// 
//
// Related Topics 链表 双指针 👍 162 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-06-19 11:03:55
 * @description 面试题 02.04.分割链表
 
 */
 
public class PartitionListLcci {
    public static void main(String[] args) {
    //测试代码
    PartitionListLcci fun = new PartitionListLcci();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(-1); // 存放小于x的节点
        ListNode dummy2 = new ListNode(-1); // 存放大于等于x的节点
        ListNode p1 = dummy1;
        ListNode p2 = dummy2;

        while (head != null) {
            if (head.val < x) {
                p1.next = head;
                p1 = p1.next;
            } else {
                p2.next = head;
                p2 = p2.next;
            }
            head = head.next;
        }

        // 连接两个链表
        p1.next = dummy2.next;
        p2.next = null; // 重要：防止链表成环

        return dummy1.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
